package com.qing.array;

import java.util.Arrays;

/**
 * 稀疏数组
 * 当一个数组中大部分元素为同一个值，或者都为0的时候，可以使用系数数组来保存该数组
 * 稀疏数组的处理方式是：
 * 记录数组有多少行多少列，有多少个不同的值
 * 把具有不同值元素的行、列、值存在一个小规模的数组中，从而缩小程序的规模
 * 0 0 1
 * 0 2 0
 * 0 0 0
 * 将上述小数组转为稀疏数组如下
 * 行        列         有效值
 * 3(多少行)  3(多少列)   2(个数)
 * 0         2          1
 * 1         1          2
 */
public class SparseArray {
    public static void operationSparseArray() {
        int length = 10;
        int width = 10;
        //定义一个二维数组 10 * 10，因为int类型，未赋值的都是默认0
        int[][] array = new int[length][width];
        array[0][3] = 9;
        array[2][6] = 9;
        //输出二位数组
        //外层遍历数组的长度
        System.out.println("输出原数组=================================================");
        for (int i = 0; i < array.length; i++) {
            //内层遍历每个数组中有多少个元素
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("将数组转为稀疏数组=================================================");
        int count = 0;
        //先获取有效值个数
        for (int[] ints : array) {
            for (int num : ints) {
                if (num != 0) {
                    count++;
                }
            }
        }
        System.out.println("有效值的个数为：" + count);
        //创建稀疏数组
        int[][] bubbleArray = new int[count + 1][3];
        bubbleArray[0][0] = length;
        bubbleArray[0][1] = width;
        bubbleArray[0][2] = count;

        int bubbleCount = 0;
        //稀疏数组赋值

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] != 0) {
                    //稀疏数组的行索引，由于第0行是（多少行，多少列，多少个有效值）已被赋值，所以索引从1开始计数
                    bubbleCount++;
                    //稀疏数组第一列是索引，所以取i
                    bubbleArray[bubbleCount][0] = i;
                    //稀疏数组第二列也是索引，取j的索引值
                    bubbleArray[bubbleCount][1] = j;
                    //稀疏数组第三列是有效值，取不为0的数
                    bubbleArray[bubbleCount][2] = array[i][j];
                }
            }
        }
        System.out.println("输出稀疏数组=================================================");
        //输出稀疏数组
        for (int i = 0; i < bubbleArray.length; i++) {
            for (int j = 0; j < bubbleArray[i].length; j++) {
                System.out.print(bubbleArray[i][j] + "\t");
            }
            System.out.println();
        }

        //还原稀疏数组
        //定义还原数组，长度从稀疏数组索引0行取值
        int[][] restoreBubbleArray = new int[bubbleArray[0][0]][bubbleArray[0][1]];
        //第一行存的长宽高，不是要用的值，所以索引从1开始
        for (int i = 1; i <= bubbleArray.length - 1; i++) {
            restoreBubbleArray[bubbleArray[i][0]][bubbleArray[i][1]] = bubbleArray[i][2];
        }
        System.out.println("输出还原稀疏数组=================================================");
        //遍历还原稀疏数组
        for (int[] ints : restoreBubbleArray) {
            for (int anInt : ints) {
                System.out.print(anInt);
            }
            System.out.print(",");
        }
    }


    public static void main(String[] args) {
        operationSparseArray();
    }
}
